package slidingWindow;

/**
 * 例子：卷尺
 */

/**
 * 模板：
 * def findSubArray(nums):
 *     N = len(nums) # 数组/字符串长度
 *     left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
 *     sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
 *     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
 *     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
 *         sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
 *         while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
 *             sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
 *             left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
 *         # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
 *         res = max(res, right - left + 1) # 需要更新结果
 *         right += 1 # 移动右指针，去探索新的区间
 *     return res
 */
public class Summary {

    /**
     * 解决问题：解决数组/字符串的子元素问题，解决一些查找满足一定条件的连续区间的性质问题。
     * “请找到满足xx的最x的区间（子串/子数组）的xx”这类问题（重点）(主要是求数组的长度，和长度相关的)
     * 1、题目分为两种类型，一种是固定窗口大小，一种是滑动窗口大小
     * 2、两类问题，求和问题和子串问题
     */
    /**
     * 算法思路：
     * 1、需要输出或则比较的结果再原数据结构中是连续排列的；
     * 2、每次窗口滑动时，只需要观察窗口两端元素的变化，无论窗口有多长，每次只操作两个头尾元素，当用到的窗口比较长时，可以显著减少操作次数；
     * 3、窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果往往要用到窗口中的元素
     */
    /**
     * 技巧：
     * 1、比较元素的种类和各个种类的数量是否一样，两种方法，一种是使用数组，一种是使用HashMap
     */
    /**
     * 总结：
     * 1、出口很重要，由哪一个边界来控制条件是否达标，边界就在哪里，就在哪里收集结果
     * 2、当左边界大于右边界时，即窗口为0.
     *
     * 总结2：应用场景的几个特点
     * 1、需要输出或比较的结果在原数据结构中是连续排列的（字符串中的连续，数组的连续元素最大和）
     * 2、每次窗口滑动时，只需要观察窗口两端元素的变化，无论窗口多长，当用到的窗口比较长时，可以明显减少操作次数
     * 3. 窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素（检查窗口中是否含有重复字符，对比窗口中元素的和）
     */
}
